// 线段树2 单点修改 多信息
// https://soj.turingedu.cn/problem/60202/

int n;
int a[maxn];
int tag[maxn << 2];

struct Node {
    ll sum, pre, suf, val;
} tr[maxn << 2];

// ll sum[maxn << 2]; // sum[now] = sum[l] + sum[r]
// ll pre[maxn << 2]; // pre[now] = max{pre[l], sum[l] + pre[r]}
// ll suf[maxn << 2]; // suf[now] = max{suf[l] + sum[r], suf[r]}
// ll val[maxn << 2]; // val[now] = max{val[l], val[r], suf[l] + pre[r]}

Node merge(const Node &l, const Node &r) { // merge the subtree
    return {l.sum + r.sum,
            max(l.pre, l.sum + r.pre),
            max(l.suf + r.sum, r.suf),
            max(max(l.val, r.val), l.suf + r.pre)};
}

void init(int now, int l, int r) { // init the tree
    if (l == r) {
        tr[now] = {a[l], a[l], a[l], a[l]};
        return;
    }
    int mid = l + r >> 1;
    init(now << 1, l, mid);
    init(now << 1 | 1, mid + 1, r);
    tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
}

void update(int now, int l, int r, int i, ll x) {
    if (l == r) {
        tr[now] = {x, x, x, x};
        return;
    }
    int mid = l + r >> 1;
    if (i <= mid)
        update(now << 1, l, mid, i, x);
    else
        update(now << 1 | 1, mid + 1, r, i, x);
    tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
}

Node ask(int now, int l, int r, int s, int t) { // ask the [s, t]
    if (s <= l && r <= t) return tr[now];       // cover
    // push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask(now << 1, l, mid, s, t);
    if (s > mid) return ask(now << 1 | 1, mid + 1, r, s, t);
    return merge(ask(now << 1, l, mid, s, t), ask(now << 1 | 1, mid + 1, r, s, t));
}
